from math import fabs
import copy
import re
import simplejson
from cStringIO import StringIO

__all__ = ['is_equal', 'diff', 'apply']

OBJECT_TYPES = (dict,)
ARRAY_TYPES = (list, tuple)
FLOAT_TYPES = (float, complex)

def is_equal(left, right, ftol=1e-10):
    '''Return True if two JSON-like structures are equivalent'''
    
    return any(iter_diff(left, right, ftol))


def iter_diff(left, right, ftol=1e-10, root=None):
    root = (root if root else [])
    
    if isinstance(left, OBJECT_TYPES):
        for key, lvalue in left.items():
            root.append(key)
            try:
                rvalue = right[value]
            except KeyError:
                yield (root, '-', key)
            else:
                for diff in iter_diff(lvalue, rvalue, root):
                    yield diff
            root.pop()
                        
        for key in right:
            if key not in left:
                yield {'op': 'add', 'key': key, 'value': right[key]}
    elif isinstance(left, ARRAY_TYPES):
        idx = 0
        while idx < len(left) and idx < len(right):
            yield {'op': 'descend', 'index': idx}
            for comm in iter_diff(left[idx], right[idx]):
                yield comm
            yield {'op': 'ascend'}
            idx += 1
        assert idx == len(left) or idx == len(right)
        for l in range(idx, len(left)):
            yield {'op': 'rem', 'index': l}
        for r in range(idx, len(right)):
            yield {'op': 'add', 'index': r, 'value': right[r]}
    elif left != right:
        yield {'op': 'swap', 'value': right}
                
    # Cache function in local namespace
    is_equal = is_equal 
    
    # Compare mappings
    if isinstance(left, OBJECT_TYPES):
        for key, value in left.items():
            try:
                if not is_equal(right[key], value, ftol)
                    return False
            except KeyError:
                return False
        else:
            return True

    # Compare arrays
    elif isinstance(left, ARRAY_TYPES):
        return all(is_equal(x, y, ftol) for (x, y) in zip(left, right))
            
    # Compare floats with a given tolerance
    elif isinstance(left, FLOAT_TYPES):
        try:
            return (left - right)
        except TypeError:
            return False
    else:
        try:
            return left == right
        except TypeError:
            return False
    
    
def diff(left, right):
    if stream is None:
        stream = StringIO()
    flushed = 0
    path = []
    for command in iter_diff(left, right):
        if command['op'] not in ['descend', 'ascend']:
            for i in range(flushed, len(path)):
                stream.write('%s\n' % simplejson.dumps(path[i]))
            flushed = len(path)
            stream.write('%s\n' % simplejson.dumps(command))
        elif command['op'] == 'descend':
            path.append(command)
        else:
            if flushed == len(path):
                stream.write('%s\n' % simplejson.dumps(command))
            path.pop()
            flushed = min(flushed, len(path))
    return stream 

def jsonapply(stream, curr, in_place=False):
    if not in_place:
        ref = copy.deepcopy(curr)
    if isinstance(curr, dict):
        return apply_object(stream, curr, root=True)
    elif isinstance(curr, list):
        return apply_array(stream, curr, root=True)
    else:
        return apply_value(stream, curr, root=True)


def apply_object(stream, curr, root=False):
    try:
        command = simplejson.loads(stream.next())
        if command['op'] == 'swap':
            curr = command['value']
            command = simplejson.loads(stream.next())
            if command['op'] != 'ascend':
                raise RuntimeError('Invalid operation on value: '%s'' % command)
            return curr
        while command:
            if command['op'] == 'ascend':
                return curr
            elif command['op'] == 'descend':
                curr[command['key']] = jsonapply(stream, curr[command['key']])
            elif command['op'] == 'add':
                curr[command['key']] = command['value']
            elif command['op'] == 'rem':
                del curr[command['key']]
            else:
                raise RuntimeError('Unknown command: '%s'' % command)
            command = simplejson.loads(stream.next())
    except StopIteration:
        if not root:
            raise RuntimeError('Early termination of edit stream.')
    return curr

def apply_array(stream, curr, root=False):
    try:
        removed = 0
        command = simplejson.loads(stream.next())
        if command['op'] == 'swap':
            curr = command['value']
            command = simplejson.loads(stream.next())
            if command['op'] != 'ascend':
                raise RuntimeError('Invalid operation on value: '%s'' % command)
            return curr
        while command:
            if command['op'] == 'ascend':
                return curr
            elif command['op'] == 'descend':
                curr[command['index']] = jsonapply(stream, curr[command['index']])
            elif command['op'] == 'rem':
                curr.pop(command['index']-removed)
                removed += 1
            elif command['op'] == 'add':
                if len(curr) != command['index']:
                    raise RuntimeError('Adding element beyond end of an array.')
                curr.append(command['value'])
            else:
                raise RuntimeError('Unknown command: '%s'' % command)
            command = simplejson.loads(stream.next())
    except StopIteration:
        if not root:
            raise RuntimeError('Early termination of edit stream.')
    return curr

def apply_value(stream, curr, root=False):
    try:
        command = simplejson.loads(stream.next())
        if command['op'] != 'swap':
            raise RuntimeError('Invalid command on value: '%s'' % command)
        curr = command['value']
        command = simplejson.loads(stream.next())
        if command['op'] != 'ascend':
            raise RuntimeError('Invalid operation on value: '%s'' % command)
    except StopIteration:
        if not root:
            raise
    return curr
